import java.util.Random;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int ret = qsort(nums,0,nums.length - 1,k);
        return ret;
    }

    public int qsort(int[] nums,int l,int r,int key) {
        if(l == r) return nums[l];
        int k = nums[new Random().nextInt(r - l + 1) + l];
        int left = l - 1,right = r + 1,i = l;
        while(i < right) {
            if(nums[i] < k) swap(nums,++left,i++);
            else if(nums[i] == k) i++;
            else swap(nums,--right,i);
        }
        //[l,left] [left + 1,right - 1] [right,r]
        int n = r - right + 1,m = right - left - 1;
        if(n >= key) return qsort(nums,right,r,key);
        else if(m + n >= key) return k;
        else return qsort(nums,l,left,key - m - n);
    }

    public void swap(int[] nums,int i,int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}